/**
 * @param 归并
 * @param {*} arr 
 * @returns nlogn
 */
function mergeSort(arr){// 将arr 分为子序列
    let len=arr.length;
    if(len<2){
        return arr;
    }
    let middle=Math.floor(len/2);// 对半分
    let left=arr.slice(0,middle);
    let right=arr.slice(middle);
    return merge(mergeSort(left),mergeSort(right));// 递归
}

function merge(left,right){
    let result=[];
    while(left.length&&right.length){
        if(left[0]<=right[0]){
            result.push(left.shift());// 在result中添加left开头的并删除
        }else{
            result.push(right.shift());
        }
    }
    while(left.length)
        result.push(left.shift());
    while(right.length)
        result.push(right.shift());
    return result;
}

var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));